import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 快速排序：冒泡排序的改进版，若处理8000000个排序，需要花费多少时间? 本人电脑花费1秒
 */
public class QuickSortDemo {
    public static void main(String[] args) {
        int[] ints = new int[]{6,1,1,2,7,-1,9,3,15,4,5,10,8};
        System.out.println("排序前数组：");
        System.out.println(Arrays.toString(ints));
        //调用快速排序
        quickSort(ints,0, ints.length-1);
        System.out.println("排序后数组：");
        System.out.println(Arrays.toString(ints));
        System.out.println("---------------------------");

        //测试快速排序时间复杂度
        //测试算法：若处理8000000个排序，需要花费多少时间? 本人电脑花费1秒
        quickSortTest();
    }

    //测试快速排序的时间复杂度
    //测试算法：若处理8000000个排序，需要花费多少时间? 本人电脑花费1秒
    public static void quickSortTest(){
        int[] arr = new int[8000000];
        //先随机生成一个容量为80000个的数组
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random()*80000);
        }
        //创建 格式化日期格式对象：
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy.MM.dd HH:mm:ss");
        //创建当前时间的对象
        Date time1 = new Date();
        //对当前时间进行格式化
        String s1 = sdf.format(time1);
        //打印
        System.out.println("排序前时间："+s1);
        //进行排序
        quickSort(arr,0, arr.length-1);
        //再次创建当前时间对象
        Date time2 = new Date();
        String s2 = sdf.format(time2);
        System.out.println("排序后时间："+s2);
    }

    //快速排序
    public static void quickSort(int[] arr,int head,int end){
        //检验一下索引值是否输入正确
        if (head > end) {
            return;
        }
        //创建头索引
        int i = head;
        //创建尾索引
        int j = end;
        //中间转换变量
        int temp = 0;
        //选择基准数（即，随机选择一个参照数），本人这里选择了数组第一个数
        int baseNumber = arr[head];

        //进行遍历排序，找到基准数应该放置的位置
        while (i < j){
            //从右到左扫描，一步一步，直到找到比基准数小的数
            while (arr[j] >= baseNumber && i < j){
                j--;
            }
            //从左到右扫描，一步一步，直到找到比基准数大的数
            while (arr[i] <= baseNumber && i < j){
                i++;
            }
            //若同时从左边找到一个比基准数大的数，从右边找到一个比基准数小的数，则两个互相交换位置
            if (i < j) {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        //将基准数，放到数组相应的位置中去
        arr[head] = arr[j];
        arr[j] = baseNumber;
        //向左递归排序,
        quickSort(arr,head,j-1);
        //向右递归排序
        quickSort(arr,j+1, end);
    }
}
